/**
 * 合并二维有序数组为一维有序数组，(归并排序)
 * 【归并排序思想】分治思想，每层递归三个步骤
 *      分解：将n个元素分成个含n/2个元素的子序列
 *      解决：用合并排序法对两个子序列递归的排序
 *      合并：合并两个已排序的子序列已得到排序结果
 * 【归并排序实现逻辑】
 *      1.将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
 *      2.将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
 *      3.重复步骤②，直到所有元素排序完毕
 */

const mergeSort = (arr) => {
    if (arr.length === 0) {
        return []
    }
    while (arr.length > 1) {
        const arrItem1 = arr.shift()
        const arrItem2 = arr.shift()
        arr.push(sort(arrItem1, arrItem2))
    }
    return arr[0]
}

const sort = (leftArr, rightArr) => {
    const result = []
    while (leftArr.length > 0 && rightArr.length > 0) {
        if (leftArr[0] > rightArr[0]) {
            result.push(rightArr.shift())
        } else {
            result.push(leftArr.shift())
        }
    }
    return result.concat(leftArr).concat(rightArr)
}

const arr = [[1, 2, 4], [2, 3, 7], [3, 5, 7], [4, 5, 8]]

console.log(mergeSort(arr))   